package Leetcode.树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: kirito
 * @Description: 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
 * @Date: 2024/2/26 11:11
 * 树中节点数目在范围 [1, 2 * 104] 内
 * 1 <= Node.val <= 105
 * 1 <= low <= high <= 105
 * 所有 Node.val 互不相同
 * @Version: 1.0
 */

public class 二叉搜索树的范围和 {
    //dfs
//    1. root节点为空
//    返回0。
//    2.root节点的值大于high
//    由于二叉搜索树右子树上所有节点的值均大于根节点的值，即均大于high，故无需考虑右子树，返回左子树的范围和。
//    3. root节点的值小于low
//    由于二叉搜索树左子树上所有节点的值均小于根节点的值，即均小于lou，故无需考虑左子树，返回右子树的范围和。
//    4.root节点的值在[lou, high]范围内
//    此时应返回root 节点的值、左子树的范围和、右子树的范围和这三者之和。
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }
        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }
        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }

    //bfs
    public int rangeSumBST2(TreeNode root, int low, int high) {
        int sum = 0;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                continue;
            }
            if (node.val > high) {
                q.offer(node.left);
            } else if (node.val < low) {
                q.offer(node.right);
            } else {
                sum += node.val;
                q.offer(node.left);
                q.offer(node.right);
            }
        }
        return sum;
    }

}
